package com.gxc.array;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
 *  例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：
 *  ​[4,3,5],4,3,3,6,7           窗口最大值：5
 *  4,[3,5,4],3,3,6,7​           窗口最大值：5
 *  4,3,[5,4,3],3,6,7​​           窗口最大值：5
 *  4,3,5,[4,3,3],6,7​           窗口最大值：4
 *  4,3,5,4,[3,3,6],7​            窗口最大值：6
 *  4,3,5,4,3,[3,6,7]​            窗口最大值：7
 *  如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
 *  请实现一个函数。
 *  （1）输入：整型数组arr，窗口大小为：w。
 *  （2）输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
 *  以本题为例，结果应该返回{5,5,5,4,6,7}。
 */
public class GetMaxWindow {

    public static void main(String[] args) {
        int[] nums = {4,3,5,4,3,3,6,7};
        int w = 3;

        int[] res = handle(nums, 3);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }

    //单调队列
    private static int[] handle(int[] nums, int w) {
        int[] res = new int[nums.length-w+1];
        LinkedList<Integer> queue = new LinkedList<>();
        int index = 0;
        for (int j = 0; j < nums.length; j++) {
            while (!queue.isEmpty() && nums[j]>nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.addLast(j);
            if (queue.peekFirst() == j-w) queue.pollFirst();
            if (j>=w-1) {
                res[j-w+1] = nums[queue.peekFirst()];

            }
        }
        return res;
    }


}
